package homework.exp06;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class K {
    static Scanner cin = null;

    static {
        try {
            cin = new Scanner(new FileInputStream(new File("src/homework/exp06/K.in")));
        } catch (IOException e) {
            cin = new Scanner(System.in);
        }
    }

    static final int MAXN = 101; // 最大节点数
    static final int INF = 0xfffff; // 表示无穷大
    static int[][] a = new int[MAXN][MAXN]; // 邻接矩阵
    static boolean[] book = new boolean[MAXN]; // 记录是否已找到最短路径
    static int[] dis = new int[MAXN]; // 保存源点到各点的最短距离
    static int n, v; // n是节点数，v是源点

    public static void main(String[] args) {

        n = cin.nextInt(); // 读取节点数
        v = cin.nextInt(); // 读取源点

        for (int i = 1; i <= n; i++) { // 初始化邻接矩阵
            for (int j = 1; j <= n; j++) {
                int t = cin.nextInt();
                if (i == j) a[i][j] = 0; // 对角线元素为0
                else if (t == 0) a[i][j] = INF; // 没有直接连接的点设为无穷大
                else a[i][j] = t; // 其他情况按输入赋值
            }
        }

        shortestPath_DIJ(v + 1); // 调用Dijkstra算法
    }

    // Dijkstra算法实现
    public static void shortestPath_DIJ(int s) {
        Arrays.fill(book, false); // 初始化book数组为false
        Arrays.fill(dis, INF); // 初始化dis数组为无穷大

        for (int i = 1; i <= n; i++) {
            dis[i] = a[s][i]; // 初始化源点到各点的最短距离
        }
        book[s] = true; // 第一个点加入到确定最短路径的集合中

        for (int i = 1; i < n; i++) { // 循环n-1次
            int u = -1, MIN = INF; // 用于找最近的点和最小值
            for (int j = 1; j <= n; j++) {
                if (!book[j] && dis[j] < MIN) { // 找dis数组中权值最小的点
                    u = j; // 待加入的点
                    MIN = dis[j]; // 更新最小值
                }
            }
            if (u == -1) break; // 如果找不到有效的u，退出循环
            book[u] = true; // 将找到的点加入到集合中
            for (int j = 1; j <= n; j++) {
                if (!book[j] && a[u][j] < INF && dis[j] > dis[u] + a[u][j]) { // 更新其他点的最短距离
                    dis[j] = dis[u] + a[u][j];
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (i == s) continue; // 跳过源点自身
            if (dis[i] >= INF) System.out.print(-1 + " "); // 如果距离为无穷大，输出-1
            else System.out.print(dis[i] + " "); // 否则输出实际距离
        }
        System.out.println(); // 换行


        cin.close();
    }
}